package com.data.algorithm.sort;



/**
 * 堆排序
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/7/17
 */
public class HeapSort {


    public static void main(String[] args) {
        int[] arr = new int[80000];
        for(int i = 0; i < 80000; ++i) {
            arr[i] = (int)(Math.random() * 8000000.0D);
        }


        Long startTime = System.currentTimeMillis();
        System.out.println("开始排序");
        heapSort(arr);
        Long endTime = System.currentTimeMillis()- startTime;

        System.out.println("排序耗时：" + endTime+"毫秒");
        System.out.println("排序耗时：" + endTime/1000+"秒");

    }
    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int arr[]){
        int temp;
        for(int i=arr.length/2-1;i >= 0;i--){
            adjusHeap(arr,i,arr.length);
        }
        for(int j = arr.length - 1;j > 0;j--){
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjusHeap(arr,0,j);
        }
    }
    /**
     * 将i对应的非叶子节点的树调整成大顶堆
     * @param arr 待调整数组
     * @param i 非叶子结点在数组中的索引
     * @param len 多少个元素继续调整
     */
    public static void adjusHeap(int arr[],int i,int len){

        int temp = arr[i];
        //k = i*2+1是i结点的左子结点
        for(int k = i*2+1;k < len;k = k *2+1 ){
            if(k+1 < len && arr[k] < arr[k+1]){
                k++;
            }
            if(arr[k] > temp){
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }

        arr[i] = temp;
    }
}
